home *** CD-ROM | disk | FTP | other *** search
/ Aminet 2 / Aminet AMIGA CDROM (1994)(Walnut Creek)[Feb 1994][W.O. 44790-1].iso / Aminet / util / cli / UnixUtils.lha / UnixUtils / Source / sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-02  |  7.3 KB  |  311 lines
  1. /*---------------------------------------------*
  2.  | sort.c - Unix-like utility.                 |
  3.  | Syntax: sort [flags] [file [file [ ... ] ]  |
  4.  | Sorts the given files (or stdin) to stdout; |
  5.  | see Syntax() for a complete description.    |
  6.  | v1.00 MLO 911225                            |
  7.  *---------------------------------------------*/
  8.  
  9. /**
  10.  | For sorting, the read lines are arranged in memory in a binary tree;
  11.  | the tree itself can be balanced (if BALANCED_TREE is defined),
  12.  | according to the algorithm of Adel'son-Vel'skij and Landis as
  13.  | described from D.E.Knuth - The art of computer programming (Addison
  14.  | Wesley) - Vol. 3, pag. 451-471. This leads to a more efficient
  15.  | searching along the tree for unbalanced input (i.e. for almost
  16.  | already sorted files), but is an exercise without pratical effect
  17.  | normally; so you would leave  BALANCED_TREE undefined.
  18.  |
  19.  | #define'ing SIMPLE generates a short version of sort, with the
  20.  | normal binary tree algorithm, and alphabetical ordering from column
  21.  | 1 as only ordering option (the only active switch is -r). This way,
  22.  | a file containing 1202 lines of ASCII text (47100 bytes total) can
  23.  | be sorted on a vanilla A500 in less than 4 seconds, against the 24
  24.  | seconds needed from c:sort (AmigaDOS 1.3: Kickstart 34.5, Workbench
  25.  | 34.28).
  26. **/
  27.  
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #ifndef SIMPLE
  31. #include <string.h>
  32. #include <ctype.h>
  33. #endif
  34. #include <libraries/dos.h>
  35. #include <proto/exec.h>
  36. #include "mlo.h"
  37. #include "sort.h"
  38.  
  39. short int abortProg = 0;                  /* "CTRL-C hit" flag */
  40. Boolean reverse = False;                  /* "Sort in reverse order" flag */
  41.  
  42. FILE *fp = NULL;
  43.  
  44. #ifndef SIMPLE
  45. static SortType method = ALPHABETICAL;    /* "Sort method" flag */
  46. static SortType divide = COLUMN;          /* "Input line division" flag */
  47. static char terminator[TERM_LEN] = " ";   /* Field separator(s) */
  48. static int start = 0;                     /* Sorting Field | Column number */
  49. char *temp1 = NULL;                       /* Temporary buffers */
  50. static char *temp2;
  51. #endif
  52.  
  53. Node *root = NULL;                        /* Binary tree root */
  54.  
  55. #ifdef BALANCED_TREE
  56. Node *critical;                           /* Critical node for rebalancing */
  57. Node *father;                             /* Father node of *critical */
  58. #endif
  59.  
  60. static void DoTheStuff(FILE *filePointer);
  61. static void Syntax(void);
  62.  
  63. void main(
  64.   int argc,
  65.   char **argv
  66. ){
  67.  
  68. /**
  69.  | Resolves the input line
  70. **/
  71.  
  72.   while (--argc) {
  73.     if ( ((*++argv)[0] == '-') ) {
  74.       switch ((*argv)[1]) {
  75.         case 'r':
  76.         case 'R':
  77.           reverse = True;
  78.           break;
  79.  
  80. #ifdef SIMPLE
  81.           default:
  82.             Syntax();
  83.       }
  84. #else
  85.         case 'f':
  86.         case 'F':
  87.           method = CASE_FOLDED;
  88.           break;
  89.         case 'n':
  90.         case 'N':
  91.           method = NUMERICAL;
  92.           break;
  93.         case 't':
  94.         case 'T':
  95.           if ((*argv)[2]) strcpy(terminator, *argv+2);
  96.              else         Syntax();
  97.           break;
  98.         default:
  99.           if (isdigit((*argv)[1])) start = atoi(*argv+1) - 1;
  100.              else                  Syntax();
  101.           divide = COLUMN;
  102.           break;
  103.       }
  104.     } else if ((*argv)[0] == '+') {
  105.       if (isdigit((*argv)[1])) start = atoi(*argv+1);
  106.          else                  Syntax();
  107.       divide = FIELD;
  108. #endif
  109.  
  110.     } else if ((*argv)[0] == '?') {
  111.       Syntax();
  112.     } else {
  113.       break;
  114.     }
  115.   }
  116.  
  117. /**
  118.  | Allocate the temporary buffers
  119. **/
  120.  
  121. #ifndef SIMPLE
  122.   if ((temp1 = calloc(2, LINE_LENGTH)) == NULL) {
  123.     puts("sort: couldn't obtain heap memory.");
  124.     exit(SYS_ABORT_CODE);
  125.   }
  126.   temp2 = temp1 + LINE_LENGTH;
  127. #endif
  128.  
  129. /**
  130.  | Reads and sorts the input file(s)
  131. **/
  132.  
  133.   if (argc) {
  134.     while (argc--) {
  135.       if ((fp = fopen(*argv, "r")) == NULL) {
  136.         printf("sort: couldn't open file \"%s\".\n", *argv);
  137.       } else {
  138.         DoTheStuff(fp);
  139.         fclose(fp);
  140.         fp = NULL;
  141.       }
  142.       ++argv;
  143.     }
  144.   } else {
  145.     DoTheStuff(stdin);
  146.   }
  147.  
  148. /**
  149.  | Final printout, and graceful exit
  150. **/
  151.  
  152.   if (root)   PrintTree(root);
  153.  
  154. #ifndef SIMPLE
  155.   free(temp1);
  156. #endif
  157.  
  158.   exit(SYS_NORMAL_CODE);
  159. }
  160.  
  161. #ifndef SIMPLE
  162. int Compare(
  163.   char *p1,
  164.   char *p2
  165. ){
  166.   int result;
  167.  
  168. /**
  169.  | Compares the two string in "p1" and "p2"; returns 0 if they
  170.  | are identical, otherwise compares them using the sorting
  171.  | criteria specified in the input line, returning a negative
  172.  | number if "p1" comes before "p2" or a positive number otherwise.
  173.  |
  174.  | Are the string absolutely identical?
  175. **/
  176.  
  177.   if (!strcmp(p1, p2))  return 0;
  178.  
  179. /**
  180.  | If not, store in p1 and p2 the pointers to the string regions
  181.  | to be compared.
  182. **/
  183.  
  184.   switch (divide) {
  185.     case COLUMN:
  186.       p1 += start;
  187.       p2 += start;
  188.       break;
  189.     case FIELD:
  190.       if (*terminator == BLANK) {
  191.         GetTokBlk(p1, start, temp1);
  192.         GetTokBlk(p2, start, temp2);
  193.       } else {
  194.         GetTokDel(p1, terminator, start, temp1);
  195.         GetTokDel(p2, terminator, start, temp2);
  196.       }
  197.       p1 = temp1;
  198.       p2 = temp2;
  199.       break;
  200.   }
  201.  
  202.   switch (method) {
  203.     case ALPHABETICAL:
  204.       result = strcmp(p1, p2);
  205.       break;
  206.     case CASE_FOLDED:
  207.       result = stricmp(p1, p2);
  208.       break;
  209.     case NUMERICAL:
  210.       result  = atoi(p1);
  211.       result -= atoi(p2);
  212.       break;
  213.   }
  214.  
  215. /**
  216.  | If the compared field matches, but the original records were
  217.  | not identical, insert them in the order they came (p1 AFTER p2).
  218. **/
  219.  
  220.   if (!result)  return 1;
  221.      else       return result;
  222. }
  223. #endif
  224.  
  225. void CheckBreak(
  226.   Boolean exitprog
  227. ){
  228.  
  229. /**
  230.  | Checks the CTRL-C flag and, the first time it is set, prints
  231.  | a warning message. If the argument is True, frees allocated
  232.  | memory and exits; no further action, if the argument is False.
  233. **/
  234.   if (!abortProg && (SetSignal(0L, SIGBREAKF_CTRL_C) & SIGBREAKF_CTRL_C))
  235.       abortProg |= BREAK_DETECTED;
  236.  
  237.   if (abortProg) {
  238.     if (!(abortProg & WARNING_PRINTED)) {
  239.       puts("sort: *** BREAK ***");
  240.       abortProg |= WARNING_PRINTED;
  241.     }
  242.     if (exitprog) {
  243.       FreeTree(root);
  244. #ifndef SIMPLE
  245.       if (temp1 != NULL) free(temp1);
  246. #endif
  247.       if (fp != NULL) fclose(fp);
  248.       exit(SYS_NORMAL_CODE);
  249.     }
  250.   }
  251. }
  252.  
  253. int CXBRK(void)
  254. {
  255.  
  256. /**
  257.  | If a CTRL-C is detected from the operating system,
  258.  | we silently defer all handling until "abortProg" is checked.
  259. **/
  260.  
  261.   abortProg |= BREAK_DETECTED;
  262.   return 0;
  263. }
  264.  
  265. static void DoTheStuff(
  266.   FILE *filePointer
  267. ){
  268.   char buffer[LINE_LENGTH];
  269.  
  270.   while (fgets(buffer, LINE_LENGTH, filePointer)) {
  271.     CheckBreak(True);
  272.  
  273. #ifdef BALANCED_TREE
  274.     father   = NULL;
  275.     critical = root;
  276. #endif
  277.  
  278.     root = InsertTree(buffer, root);
  279.  
  280. #ifdef BALANCED_TREE
  281.     BalanceTree(buffer);
  282. #endif
  283.  
  284.   }
  285. }
  286.  
  287. static void Syntax(void)
  288. {
  289.  
  290. #ifdef SIMPLE
  291.   puts("\nUsage:   sort [-r] [file [file [ ... ] ] ]");
  292. #else
  293.   puts("\nUsage:   sort [-r][-f|-n][+N|-N][-tx] [file [file [ ... ] ] ]");
  294. #endif
  295.  
  296.   puts("Purpose: sorts the records read from the input file(s), or from");
  297.   puts("         stdin, to stdout.");
  298.   puts("    -r : reverse order sorting");
  299.  
  300. #ifndef SIMPLE
  301.   puts("    -n : numeric sorting                  \\ Default: alphabetic");
  302.   puts("    -f : folds uppercase to lowercase     /          sorting");
  303.   puts("    -N : sorts starting at column N       \\ Default: start");
  304.   puts("    +N : sorts respect to field N         /          at column 1");
  305.   puts(" -t... : separator character(s) between fields (default: space)");
  306. #endif
  307.  
  308.   puts("");
  309.   exit(SYS_NORMAL_CODE);
  310. }
  311.